A purpose of channel encoding is to ensure reliable transmission of information, the complexity of implementation of a channel encoding scheme mainly lies at a decoding end, and a decoder is typically a critical part of the channel encoding scheme. A decoder can be either implemented using hardware, i.e. using hardware logic units to construct the decoder; or implemented using software, i.e. using a general processor (CPU) to implement the decoder through programs; a decoder can also be implemented using an implementation method combining software and hardware.
Low Density Generator Matrix Codes (LDGC) generally mean: their generator matrix is a sparse binary matrix (i.e. matrix elements are comprised of 0 and 1 alone) of Class I codes, including structured LDGC and non-structured LDGC such as Raptor codes, etc.
The LDGC is suitable for performing forward error correction (FEC) to an erasure channel. During a data transmission process, if a data packet received at a receiving end has any check error, an erroneous data segment is discarded, which is equivalent to performing erasing. LDGC can effectively countermine loss of data.
Also, LDGC is a kind of linear block code, all elements in its generator matrix (encoding matrix) come from a two element field (GF(2) field), i.e. the elements in the generator matrix are comprised of 0 and 1 alone; and its nonzero elements are typically sparse, i.e. the number of “1”s in the matrix only accounts for a very small percentage in the total number of elements in the matrix; moreover, LDGC is also a kind of system code, i.e. a first K bits of code words generated by encoding K-bit information bits by using an LDGC generator matrix are the same as the information bits. All calculations involved during the LDGC encoding/decoding process are calculations in the GF(2) field.
A generator matrix of structured LDGC also has other characteristics, and can be obtained by expanding and modifying a very small basic matrix; in particular, a square matrix to which its first L rows correspond is generally an upper triangular or lower triangular matrix. While a generator matrix of LDGC that do not have any structured feature such as Raptor codes is a random binary matrix. Gldgc will be used below for collectively indicating an LDGC generator matrix, when it is necessary to indicate LDGC generator matrices separately, Gstruct will be used for indicating a transposition of a generator matrix of structured LDGC, Grandom will be used for indicating a transposition of a generator matrix of LDGC that do not have any structured feature (the matrix can be referred to as a non-structured LDGC generator matrix), and in particular Grandom will include a generator matrix of Raptor codes.
In the following statements, any “vector” or “matrix” with a subscript of a small letter t will all indicate a transposition of an original “vector” or “matrix”, such vector or matrix and its transposition look exactly the same in their contents, and sometimes can indicate the same object. For example, Gldgct is defined as a transposition of Gldgc, It as a transposition of I, and Rt as a transposition of R, because either I or R is a row vector, herein both It and Rt are column vectors; in the following, Gstruct and Grandom will be used respectively to indicate their separate generator matrix Gldgct after transposition.
FIG. 1 is a schematic illustration of Gldgct, which is an LDGC generator matrix after transposition. As shown in FIG. 1a, a square matrix to which a first L rows in a structured LDGC generator matrix Gstruct correspond is generally an upper triangular or lower triangular matrix. As shown in FIG. 1b, a square matrix to which a first L rows of Raptor codes correspond is a random matrix, which does not have the characteristics of an upper triangular or lower triangular matrix. Wherein x and y in the figure may be 0.
The encoding with LDGC involves first obtaining intermediate variables by using a corresponding relationship between information bits (i.e. data to be sent) and intermediate variables in system codes, and then obtaining after-encoding code words by multiplying the intermediate variables with a generator matrix. Specifically speaking, an encoding process involves first generating a sequence s of L bits by filling d=L−K known bits in an original information sequence m of K bits, then obtaining an intermediate variable sequence I of L bits by solving a system of equations according to the relation of the system of equations: I×Gldgc(0: L−1, 0: L−1)=s, then obtaining a code word sequence C′ldgc of N+d bits (containing d filled bits) by multiplying the intermediate variables with a generator matrix, i.e. I×Gldgc(0: L−1, 0: N+d−1), the d filled bits in C′ldgc do not need to be transmitted, therefore what is really transmitted is a code word sequence Cldgc of N bits. After Cldgc passed through a channel (may be erased), a code word sequence received at a receiving end is R. Wherein s is a vector of 1×L; I is a vector of 1×L; R is a vector of 1×N, and its transposition Rt is a vector of N×1; Gldgc(0: L−1, 0: L−1) is an L×L square matrix, which is generally an upper triangular or lower triangular matrix, and Gldgc(0: L−1, 0: N+d−1) is an L×(N+d) matrix. For the detailed process of encoding, please refer to the patent “An encoding method and device, a decoding method and device for low density generator matrix code”.
FIG. 2 is a flowchart of a decoding method for low density generator matrix codes. As shown in FIG. 2, the decoding process includes the following steps:
201: obtaining Re by filling a known bit sequence of the length of d=L−K in the corresponding positions of a received code word sequence Rt, such as 1, 1, . . . , 1, and by deleting code word symbols erased by a channel;
wherein K is the length of original information bits, and L is the encoded length of the original information bits after filling.
202: obtaining an erasure generator matrix Ge by performing row erasing (deleting) processing to Gldgct according to how the received code word sequence Rt has been erased.
FIG. 3 is a schematic illustration of performing erasing processing to the generator matrix according to how the received code word sequence Rt has been erased. As shown in FIG. 3, the first L rows of the generator matrix Ge after erasing processing no longer represent a lower triangular square matrix.
Assuming that XT symbols: {ri, rj, . . . , rp . . . rx} in R=(r0, r1, . . . rN+d−1)T after filling a known bit sequence has been erased by a channel; wherein XL symbols {ri, rj, . . . , rp} in the first L symbols have been erased by a channel; then Xset={i, j, . . . , p, . . . , x}; XsetL={i, j, . . . p}. Ge is simply obtained by erasing the {i, j, . . . , p, . . . , x}-th rows in Gldgct accordingly, and now because several rows have been erased, the matrix in Ge is no longer exactly diagonalized, as shown in FIG. 3(c).
203: obtaining an intermediate variable It by solving a system of equations Ge×It=Re;
204: obtaining st according to the relation of the system of equations Gldgct(0:L−1,0:L−1)×It=st, and obtaining an original information sequence m of K bits by deleting the filled d known bits from st, thereby completing LDGC decoding.
During the above-mentioned decoding process, the most critical step is obtaining the intermediate variable It, and this would typically require solving a large scale system of binary linear equations. As far as engineering is concerned, methods such as Gauss elimination or iteration can be used for solving a system of linear equations; according to the characteristics of LDGC, the Gauss elimination method is more suitable for LDGC decoding. Therefore, the speed of the Gauss elimination process will directly affect the speed of LDGC decoding.
During the process of obtaining the intermediate variable It according to the relation of a system of equations Gldgct(0: N+d−1,0: L−1)×It=Rt (Gldgct is written as Ge and Rt is written as Re when there is channel erasure, and the above-mentioned relation of a system of equations is Ge×It=Re), the ongoing Gauss elimination has to perform three kinds of elementary transformations to Gldgct (written as Ge when there is channel erasure), i.e. “row permutation, row addition and column permutation”. According to the principles of linear algebra, in order to ensure the correctness of the system of equations, while performing elementary transformation to Gldgct (Ge), it is necessary to perform the following corresponding processing to It and Rt (or Re when there is channel erasure):
1) row permutation, if the i-th row and the j-th row of Gldgct (Ge) are permuted, the i-th bit and the j-th bit of Rt (Re) need to be permuted;
2) row addition, if the i-th row and the j-th row of Gldgct (Ge) are added, the i-th bit and the j-th bit of Rt (Re) need to be added (addition modulo 2);
3) column permutation, if the i-th column and the j-th column of Gldgct (Ge) are permuted, the i-th bit and the j-th bit of It need to be permuted.
Because the final result required is to get It, while the elements in It have been permuted correspondingly during column permutation of Gldgct (Ge), it is necessary to record how the It has been permuted to make it easier for the subsequent inverse permutation process. As far as engineering is concerned, how the It has been permuted can be recorded through an array. However, Rt is not the data ultimately desired, so it can be processed directly, and it is not necessary to record how it has been processed.
Because these transformation relationships are strictly corresponding to each other, and the complexity of Gauss elimination is mainly reflected in the processing of Gldgct (Ge), for easy descriptions below, for any elementary transformation against Gldgct (Ge), the corresponding processing to It and Rt (Re) has to be performed in strict accordance with the above-mentioned three situations. In order to focus on key points, the description of processing to It and Rt (Re) may be simplified below sometimes.
Generally, the complexity (amount of calculation) in the implementation of Gauss elimination is mainly reflected in the “row addition” operation of the matrix. Because all elements of Gldgct come from the GF(2) field, the addition operation of two rows in Gldgct (Ge) is the “addition modulo 2” operation, for example,
row_i, which is the contents of the i-th row, is: (1,0,0,0,0,1,0,1);
row_j, which is the contents of the j-th row, is: (1,1,0,0,0,1,1,1);
If an operation that uses row_i to eliminate row_j happens during Gauss elimination process, this is equivalent to:row—j=row—i+row—j=(1,0,0,0,0,1,0,1)+(1,1,0,0,0,1,1,1)=(0,1,0,0,0,0,1,0);
herein “+” means addition (addition modulo 2) in the GF(2) field;
It is seen from the above-example that because all elements in Gldgct come from the GF(2) field, that is the value of an element can only be either 0 or 1, if these 0 and 1 elements are stored directly, that is each bit element occupies one storage unit or occupies one processor word (which is generally 32 bits), when the code length is large, Gldgct (Ge) would require a very big storage space; moreover, the row addition operation is very time-consuming because it has to perform addition modulo 2 to each element, respectively.